Nằm cách xa đất liền, nhưng do nằm ở vị trí thuận lợi trên đường hàng hải nối liền Âu-Á nên Côn Đảo sớm được người phương Tây biết đến. Theo tài liệu "Relation des Voyages par les Arabes et Persans dans l’Inde et la Chine dans le IX siècle de l’Ère Chrétienne", dẫn theo ghi chép của thương nhân Ả Rập sống ở thế kỷ thứ IX là Soleyman cho biết "sau khi rời Senef, các thủy thủ phải mất mười ngày mới đến được Sender-Foulat".[7] Một tài liệu khác, "Relations de Voyages et Textes Géograaphiques Arabes, Persans et Turks Relatifs à l’Extrême-Orient", cũng dẫn theo ghi chép của Sulaymân (một cách phiên âm khác từ Soleyman), ghi địa danh này là Cundur-fũlát. Gabriel Ferrand cũng chú giải thêm: Cundur-fũlát là cách đọc cổ, Sundur-fũlát là cách đọc hiện đại; có nghĩa là những hòn đảo trái bí (les iles de la courge) trong tiếng Mã Lai. Ông cũng khẳng định đó chính là đảo Poulo Condore, tọa lạc tại địa điển cách đồng bằng sông Mékong bốn mươi dặm về phía Nam;[8] tương ứng vị trí quần đảo Côn Đảo ngày nay.

Trong tác phẩm Marco Polo du ký, thương gia người Ý Marco Polo có ghi chép vào năm 1294, đoàn thuyền buôn 14 chiếc của ông trên đường từ Trung Hoa về nước bị một cơn bão nhấn chìm mất 8 chiếc; số còn lại đã dạt vào trú tại Côn Đảo[9], được ông ghi nhận với tên gọi Poulo Condore.[10]